Rehema bắt đầu sự nghiệp diễn xuất của cô trong sản xuất năm 2008 của Mira Nair's Maisha Film Lab, Downcast, nơi cô đóng vai một bà nội trợ.

Vai diễn đột phá của cô là Mary người giúp việc ở Imani đã giành được hai giải thưởng; Giải thưởng Học viện điện ảnh châu Phi cho nữ diễn viên triển vọng nhất năm 2010[4], chia sẻ giải này với Chelsea Eze và giải Nữ diễn viên xuất sắc nhất tại Liên hoan phim châu Phi của Cordoba, Tây Ban Nha năm 2010.[5][6] Bộ phim cũng giành được giải thưởng Phim điện ảnh Châu Phi cho phim hay nhất bằng tiếng Phi. Rehema cũng nhận được sự công nhận từ nhà phê bình Vard Boyd Van Hoeij, người đã viết, "Rehema Nanfuka, là một người giúp việc đau khổ trong phân khúc tốt thứ hai, gây ấn tượng với tính cách yên tĩnh của cô ấy."[7] và nhà phê bình Hollywood Neil Young viết, "Nanfuka và Buyi là những diễn viên hấp dẫn và đối phó tốt với các nhân vật ít được quan tâm."[8]

Năm 2013, cô đóng vai chính trong bộ phim Imbabazi của Joel Karekezi, The Pardon, một bộ phim về cuộc diệt chủng Rwanda, trong đó cô được đề cử giải Nữ diễn viên xuất sắc nhất tại Liên hoan phim Châu Phi tại Khouribga, Maroc năm 2015.

Rehema đóng vai Suzanna trong Yat Madit vào năm 2016 cùng với Gladys Oyenbot và Michael Wawuyo Jr. Với vai diễn này, cô giành giải thưởng cho nữ diễn viên xuất sắc nhất tại Liên hoan phim Uganda năm 2017.[9][10][11]